This invention considers the task allocation problem in a multi-processor system. Given a set of software tasks to be run in a multi-processor system, the software tasks are normally distributed to the individual processors. The tasks allocation is usually done statically, and tasks do not migrate across the processors.
The task allocation algorithms attempt to maximize aggregate performance of task executions of the multiple processors while performing task allocation. Traditional algorithms for task allocation have dealt mostly with independent tasks with no interactions. However, in real life scenarios, tasks are dependent on each other and such dependencies slow down the progress of task execution especially if the tasks reside in different processors. As a result, the aggregate performance of M processors does not converge to M times the performance of a single processor, which is well known limitation of multi-processor systems.
The task allocation method described in this invention considers task dependencies while performing task allocation. The task dependency can cause blocking of a task execution while waiting for the resolution of the dependency. While allocating the tasks to the processors, the potential blocking time is considered, and finding the best allocation that will have least blocking time is attempted to achieve maximum system performance.